Roman Calculator Repair

How do you know that a program works? Julius Caesar Enterprises has constructed a program they claim will convert Roman numerals to their decimal equivalents. See if it works, fix it if it fails, and submit a bill for consultant services.

Problem Statement

A programmer brings you the first program in the Python Code section and claims that it is a solution to the problem described in Roman Calculator Construction. The programmer also shows you the program's output for a number of test cases:

Roman numeral? I
1
Roman numeral? IX
9
Roman numeral? X
10
Roman numeral? XI
11
Roman numeral? XII
12
Roman numeral? XIV
14
Romannumeral? XL
40
Roman numeral? XLIX
49
Romannumeral? CMXCVII
997
Roman numeral? MCMXCIX
1999

Determine whether the program solves the problem. If it solves the problem, provide a complete set of test data. If it does not solve the problem point out the program's bugs to the programmer so she can fix them.

Analysis

11.1 Review the rules for Roman numbers given in Roman Calculator Construction. Show that the new program performs correctly for all the test cases in the problem statement.

Testing

11.2 Suppose another student in the class said, "Of course the program works: it gives the correct answers for lots of test cases. I am happy when my program works for one case." Explain why you agree or disagree.

Testing

11.3 Are the test cases in the problem statement sufficient to determine whether the program performs correctly? Why or why not.

Preparation

This case study introduces the use of recursion. No previous introduction to recursion is necessary.

Understanding the Program

How does one start to evaluate this program?

One way to try to get more information about the program is to run it, trying more test cases to see what answers they produce. Quite a few test cases have already been tried, and any new ones we would devise at this point would be mere "stabs in the dark." In order to get a better idea of how to test the program, we examine its code. Testing by itself can never completely show that a program works, so we must examine the code to convince ourselves of its correctness.

We focus on the program's flow of control. To understand the flow of control, we read the program from back to front, as we did in The Calendar Shop.

Stop & Help

What other aspects of the program might be interesting to examine besides its flow of control?

What does the main program do?

The main program looks like a typical "driver" program. It loops forever, apparently reading a Roman numeral, somehow converting it to a decimal, and printing it out. We guess that ReadlnRoman does both the reading and the conversion (since there is nothing else in the main program that can do this), and that it reads one Roman numeral per line (just like input). We check the output supplied by the programmer to verify our hunch.

Stop & Help

Compare this main program to the one in Roman Calculator Construction.

What does ReadlnRoman do?

Moving to ReadlnRoman, we note that it has a variable parameter, valtoReturn, in which it is probably returning a value. It prints a prompt, then waits for input (the eoln check does this). If an empty line is typed, the value to return is 0. Otherwise, ReadlnRoman calls ReadRoman. We conclude that ReadRoman will fill valToReturn with the decimal value of the Roman numeral typed by the user.

Stop & Help

Compare ReadlnRoman to the input code in Roman Calculator Construction.

What does ReadRoman do?

Next we look at ReadRoman. It reads a character into romanDigit, a variable declared locally. It stores the character's decimal equivalent computed by Translation - into romanInt. It then checks to see if all the characters in the line have been read. This is the base case of a recursive function. If all the characters in the line have been read - if eoln is true - it assigns romanDigit's decimal equivalent to valToReturn and returns. Otherwise, it calls itself and tests the returned value. This is a recursive function. Things are getting complicated!

Stop & Predict

How do programmers figure out what recursive functions do?

Can we trace this function?

It often makes sense to "play computer" and trace the action of complicated functions to understand them, so we try that with ReadRoman. Playing computer on a recursive function, however, involves a lot of bookkeeping.

What is special about tracing recursive subprograms?

To execute a recursive function, the program must keep track of where to return. It must also save values of local variables and value parameters and restore those values when it returns. This is all much easier to do by computer than by hand.

Stop & Predict

What values are best for tracing recursive solutions?

We trace recursive functions with the simplest arguments that will give us useful information. By "useful information," we mean information that results in being able to predict how the function will behave without having to consult the code.

In a recursive function, though, this involves predicting what the function will do while trying to understand it, since a recursive function calls itself. A good way to trace recursive functions is to start with a small case and then try a slightly larger case that involves the case already tested. We do this until we notice the pattern of the computation and are able to predict the result of the recursion without looking up the results of previous tests.

What values should be used to trace ReadRoman?

We plan to trace a series of progressively more complex cases to understand ReadRoman.

• First, we'll try a bunch of small examples the base cases of the recursion - where we can keep track of the results.
• Second, we'll try some slightly larger examples. For the recursive call we plan to look up the result in the small examples we already tried.
• Third, we'll keep trying larger and larger examples, always building on the simpler ones, until it is clear how ReadRoman works.

Stop & Help

Explain why these steps are necessary to figure out whether the program works for large examples.

How does ReadRoman work on one-digit Roman numerals?

The smallest cases are one-digit Roman numerals. We start with X and follow the steps:

First we read X into romanDigit.
Then we find the decimal value of X by calling Translation, and we store the result-10-into romanInt.
We've reached the end of the line, so we copy romanInt's value into valToReturn and return.

What does the trace reveal?

The value returned and printed is correct. We note that the processing for any single-digit Roman numeral is identical except for the value returned by Translation. Translation looks correct, so we conclude that ReadRoman will work correctly for any single-digit Roman numeral. We note also that the programmer's test data included two single-digit numerals, and the results were correct.

Stop & Help

Trace the action for V.

How does ReadRoman work on two-digit Roman numerals?

Now we try a Roman numeral with two digits. We choose XI. Playing computer, we proceed as follows:

We read X into romanDigit.
We find the decimal value of X by calling Translation, and we store the result-10-into romanInt.
We're not at the end of the line yet, so we call ReadRoman recursively.
We read I into a new copy of romanDigit.
We store the decimal value of I, 1, into a new copy of romanInt.
We are at the end of the line, so we copy 1 into valToReturn and return.
Back in the first ReadRoman, we compare its romanInt value, 10, with the value in valToReturn, 1.
romanInt's value is larger, so we add 10 to valToReturn and return.
As the test output confirms, valToReturn now correctly contains 11.

Stop & Help

Trace VI, another two-digit Roman numeral.

How does formatting help with tracing a recursive function?

Note the indenting of the trace at each recursive call. Indenting the trace in this way helps us keep track of where to return from the recursive call.

What other aspects of the program can be tested with two digit Roman numerals?

The first two-digit number involved addition. Now we try a test case that involves subtraction, IX:

We read I into romanDigit.
We store 1, the decimal value of I, into romanInt.
We're not at the end of the line yet, so we call ReadRoman recursively.
We read X into a new copy of romanDigit.
We store the decimal value of X, 10, into a new copy of romanInt. We are at the end of the line, so we copy 10 into valToReturn and return.
Back in the first ReadRoman, we compare its romanInt value, 1, with the value in valToReturn, 10.
romanInt's value is smaller, so we subtract 1 from valToReturn and return.

As expected from the test output, valToReturn now contains 9, the correct value. The differences between IX, XI, and other two-digit Roman numerals again occur only in Translation, so we conclude that ReadRoman works for two-digit Roman numerals.

Stop & Help

Trace the action for IV to be sure it works.

How does ReadRoman work on three-digit Roman numerals?

To make sure we have a good idea of the action in ReadRoman, we trace it on a three-digit Roman numeral. Again we choose a value that has already been tested so that we can check our work against the data the programmer has provided. XIV seems as if it would be a good test case, since it involves both addition and subtraction of intermediate values. The value we expect is 14. Here's the trace

We read X into romanDigit.
We store its decimal value, 10, into romanInt.
We're not at the end of the line yet, so we call ReadRoman recursively.
We read I into a new copy of romanDigit.
We store its decimal value, 1, into a new copy of romanInt.
We are still not at the end of the line, so we call ReadRoman recursively.
We read V into a third copy of romanDigit.
We store 5 into a third copy of romanInt.
We are at the end of the line, so we copy 5 into valToReturn and return.
Back in the second ReadRoman, we compare its romanInt value, 1, with the value in valToReturn, 5.
romanInt's value is smaller, so we subtract it from valToReturn (leaving 4) and return.
Back in the first ReadRoman, we compare its romanInt value, 10, with the value in valToReturn, 4.
romanInt's value is larger, so we add 10 to valToReturn and return.
As we expected, valToReturn now contains 14.

Stop & Help

Trace ReadRoman on another three-digit value.

What does tracing ReadRoman reveal?

We now have a good idea of how ReadRoman works. It collects the Roman digits as it proceeds through the recursion. Once it has collected them all (and reached the end of the input line), it accumulates the decimal translation by adding or subtracting the various digit values.

What template does ReadRoman use?

The action of ReadRoman resembles an example commonly used in textbooks to introduce recursion, that of printing an input line backward:

def WriteBackward():
ch = ''
if not eoln:
ch = input()
WriteBackward()
print(ch)

The example above is the simplest form of recursion that's not a tail recursion, that is, that involves some processing after returning from the recursive call. The trace pattern of WriteBackward is

read
read
read
.
.
.
write
write
write

ReadRoman is more complicated. Its trace pattern is

read
read
read
.
.
.
compute
compute
compute

as the analysis revealed.

Stop & Predict

Suppose there were no more characters in the input line when ReadRoman was called. What would happen?

Can ReadRoman ever run off the end of the input line?

Another difference between WriteBackward and ReadRoman is that Write Backward checks for end of line before it reads a character, and ReadRoman does not. Can this cause a problem?

To find out, we assume that ReadRoman is somehow entered with no more characters to read in the input line, that is, with eoln true. Now we work backward to see how ReadRoman could have been called in such a state. There are two calls to ReadRoman, one in ReadRoman itself (the recursive call) and the other in ReadlnRoman. Examining these two calls, we find that both are preceded by a call to eoln. These are executed only where eoln returns false. Thus ReadRoman cannot be called at the end of the line.

Analysis

11.4 What would happen if an illegal Roman digit were entered as input to ReadRoman?

Modification

11.5 Modify the first version of the program so that it detects an illegal Roman digit. If an illegal digit is detected the program should print a message and exit.

Analysis

11.6 Explain why ReadRoman is not a tail-recursive program.

Reflection

11.7 Suppose a classmate said, "Why are we solving this problem again? We already have a solution." Explain why you agree or disagree.

Modification

11.8 Add output statements to the program to enable it to produce trace output automatically.

Reflection

11.9 Describe how tracing a recursive program helps one understand how it works.

Reflection

11.10 Describe what information is provided by tracing a recursive program that is not provided merely by running it on sample data.

Testing the Program

We consider doing more analysis of the program by hand or running additional test cases. Looking over the test cases supplied by the programmer, we decide to run the program to try a few of our own.

Stop & Predict

What other test cases should be tried?

What additional tests are needed?

Roman Calculator Construction and Is It Legal? identify criteria for choosing test data. These include single Roman digits, combinations of Roman digits without prefixes, and data containing one or more prefixes, in particular, a case that starts with a prefix. The test cases provided by the programmer include most of these, but there are a few holes.

Additonal tests yield the following (annotated) output:

Roman numeral? C (trying another simple case)
100
Roman numeral? CLX (more simple cases)
160
Roman numeral? CLXX (double digit)
170
Roman numeral? CXL (prefix without a following digit)
140
Roman numeral? CXLI (prefix with a following digit)
141
Roman numeral? CLXXI (interior double digit)
151

A wrong answer! Let's look for some more.

Roman numeral? XXI (what part of CLXXI caused the problem?)
1

Another wrong answer! Let's try a value with a triplet.

Roman numeral? III (simplest triple digit value)
1

When do double digits fail? XXI caused an error, but XII didn't. Let's try some more.

Roman numeral? X (just making sure)
10
Roman numeral? XX (double digit alone)
10
Roman numeral? XXI (double digit preceding a digit; wrong answer!)
1
Roman numeral? XXX (another triple digit; another wrong answer!)
10

We're onto something here. The problem may involve interior sequences of Roman digits. Let's go back to ReadRoman and test III by hand.

We read I into romanDigit.
We store 1 into romanInt.
We're not at the end of the line yet, so we call ReadRoman recursively.
We read I into a new copy of romanDigit.
We store 1 into a new copy of romanInt.
We're not at the end of the line yet; we call ReadRoman recursively.
We read I into a new copy of romanDigit and store 1 into a new copy of romanInt.
We are at the end of the line, so we copy 1 into valToReturn and return.
Back in the second ReadRoman, we compare its romanInt value, 1, with the value in valToReturn, 1.
romanInt's value is the same (not smaller), so we add 1 to valToReturn and return.
valToReturn now contains 2.
Back in the first ReadRoman, we compare its romanInt value, 1, with the value in valToReturn.
romanInt's value is smaller, so we subtract 1 from valToReturn and return

Aha! valToReturn contains 1, not 3.

Stop & Predict

Describe the problem.

What went wrong?

The last subtraction should have been an addition; that is, romanInt should have been added to valToReturn rather than subtracted from it. Checking the code to find the reason for the subtraction, we find that the comparison was incorrect. Instead of comparing the current digit's value with the following digit's value, the program compared it with the accumulated value returned for the rest of the input.

How can the bug be fixed?

The program really needs two pieces of information from the recursive call, not just one. The first is the accumulated value of the Roman numeral; that's what ReadRoman is currently passing back. The other is the digit immediately to the right of the digit currently being examined (or perhaps its value - either would work), in order to make the correct comparison to decide whether to add or subtract the current digit from the total.

Analysis

11.11 Prepare a written description of the bug for the person who wrote this version of ReadRoman. Include at least three examples.

Analysis

11.12 Explain why programmers generate a set of test cases in advance of writing the code.

Analysis

11.13 If your Python environment includes a debugger that allows you to interrupt a program at a designated point, describe good places at which this program could be interrupted to help debug it.

Reflection, Analysis

11.14 Explain why the accumulation bug probably got into the code.

Modification

11.15 Modify the current version of ReadRoman so that it detects illegal sequences of the same Roman digit such as VV, XXXX, etc. The program should print a message and ask for another Roman numeral to convert if an illegal sequence is detected.

A Possible Fix

The programmer responds to the bug description, suggesting a fix with the rewritten functions that appear in the Python Code section.

Stop & Predict

Examine this code. Keep a list of the questions you have and the problems you note.

What are the differences between the new version and the previous version?

First we examine the differences between this and the original version. ReadRoman has an extra parameter, lastRoman, of type char. Addition of this parameter is the only change to ReadlnRoman. The value of lastRoman is set when eoln is true following the read, and it is passed as a parameter in the recursive call to ReadRoman. The comparison between romanInt and valToReturn is replaced by a comparison between romanInt and Translation(lastRoman).

Do the differences address the bug found in the first version?

It appears that lastRoman holds the digit immediately to the right of the digit currently being examined. If so, the programmer has fixed the problem found in the previous version.

Does the program handle all previously tested cases?

We run all the previously tested cases and find that the program handles them correctly. The annotated output:

Roman numeral? CLXXI (buggy cases from version 1;)
171
Roman numeral? XXI
21
Roman numeral? III
3
Roman numeral? XXX
30
Roman numeral? X (simple case)
10
Roman numeral? XVI (simple addition)
16
Roman numeral? XVII (double digit at the end of the numeral)
17
Roman numeral? XVIII (triple digit at the end of the numeral)
18
Roman numeral? XIV (prefix with nothing following it)
14
Roman numeral? CXL (another one)
140
Roman numeral? XC (an even easier one)
90
Roman numeral? CLXXXI (interior triple digit)
181
Roman numeral? CCCXXX (two triple digits)
330
Roman numeral? CCCXXXVI (two interior triple digits, no prefix)
336
Roman numeral? CCCXXXIV (two interior triple digits with a prefix)
334
Roman numeral? CCCXXXVIII (three triple digits)
338

Stop & Predict

What tests are still needed?

How should the revised code be analyzed?

Since the revision to the program is the addition of the lastRoman parameter, it makes sense to analyze how the new parameter works. We assume, because of its name, that lastRoman is the Roman digit immediately to the right of the digit currently being examined. When lastRoman is the last digit in the line and the eoln test succeeds, it gets passed back. That is correct. So far, so good. Also, romanInt gets compared to the translated value of lastRoman. This is the test missing from the previous version of the program.

One thing appears a bit odd. We note that lastRoman is not set when the program is not at the end of the line.

Stop & Consider

Compare your examination of this program with that of the experts. What are the differences?

What does a trace reveal?

We now trace the new ReadRoman, focusing in particular on lastRoman. We use a Roman numeral that was handled incorrectly before: LXXX.

Stop & Predict

Is LXXX a good choice for tracing? Why or why not?

We read L into romanDigit and store 50 into romanInt.
We're not at the end of the line yet, so we call ReadRoman recursively.
We read X into a new copy of romanDigit and store 10 into a new copy of romanInt.
We're not at the end of the line yet, so we call ReadRoman recursively.
We read X into a new copy of romanDigit and store 10 into a new copy of romanInt.
We're not at the end of the line yet, so we call ReadRoman recursively.
We read X into a new copy of romanDigit and store 10 into a new copy of romanInt.
We are at the end of the line, so we store X into lastRoman and 10 into valToReturn and return.
Back in the third ReadRoman, we compare its romanInt value, 10, with the decimal value for lastRoman, 10.
romanInt's value is the same (that is, not smaller), so we add 10 to valToReturn (giving 20) and return.
Back in the second ReadRoman, we compare its romanInt value, 10, with the decimal value for lastRoman, 10.
romanInt's value is the same (that is, not smaller), so we add 10 to valToReturn (giving 30) and return.
Back in the first ReadRoman, we compare its romanInt value, 50, with the decimal value for lastRoman, 10.
romanInt's value is larger, so we add 50 to valToReturn and return.

What does the trace of ReadRoman reveal?

For LXXX, the new ReadRoman computed the correct decimal value. The X, the last Roman digit, got passed back in lastRoman all the way to the beginning of the recursion. This leads us to wonder about prefixes that don't involve the last Roman digit.

Stop & Predict

Devise test cases with prefixes applied to some Roman digit other than the last one.

What are the test results?

The tests reveal a problem:

Roman numeral? CXL (one prefix)
140
Roman numeral? CXLIV (two prefixes; wrong answer!)
164
Roman numeral? XLIV (simpler version; also wrong!)
64

What happens with a trace of XLIV?

We trace ReadRoman on XLIV.

We read X into romanDigit and store 10 into romanInt.
We're not at the end of the line yet, so we call ReadRoman recursively.
We read L into a new copy of romanDigit and store 50 into a new copy of romanInt.
We're not at the end of the line yet, so we call ReadRoman recursively.
We read I into a new copy of romanDigit and store 1 into a new copy of romanInt.
We're not at the end of the line yet, so we call ReadRoman recursively.
We read V into a new copy of romanDigit and store 5 into a new copy of romanInt.
We are at the end of the line, so we store V into lastRoman and 5 into valToReturn and return.
Back in the third ReadRoman, we compare its romanInt value, 1, with the decimal value for lastRoman, 5.
romanInt's value is smaller, so we subtract 1 from valToReturn (giving 4) and return. So far, so good.
Back in the second ReadRoman, we compare its romanInt value, 50, with the decimal value for lastRoman, 5.
romanInt's value is greater, so we add 50 to valToReturn (giving 54) and return.
Back in the first ReadRoman, we compare its romanInt value, 10, with the decimal value for lastRoman, 5.
romanInt's value is larger, so we add 10 to valToReturn and return.

What does the trace reveal?

The last step of the trace displays a bug: romanInt should have been compared with 50 (the decimal value for L), not 5. It appears that for any Roman numeral whose digits have the pattern

low1 high1 low2 high2

the program ends up comparing low1 with high2 rather than with high1.

What fix is needed?

We were correct in asking why lastRoman was not set in all cases. Now we know that lastRoman needs to be updated in the code executed when eoln is false. The fix appears in boldface in this rewritten version of ReadRoman:

def ReadRoman():
global id
global romanDigits
global valToReturn
global lastRoman
romanDigit = romanDigits[id]
romanInt = Translation (romanDigit)
id += 1
if id < len(romanDigits):
ReadRoman()
if romanInt < lastRoman:
valToReturn -= romanInt
else:
valToReturn += romanInt
lastRoman = romanInt
else:
valToReturn = romanInt
lastRoman = romanInt

Testing

11.16 What shorter Roman numeral would have demonstrated the bug in ReadRoman? Explain why.

Testing

11.17 Test the revised version of ReadRoman with all the test cases devised so far. Show your results. Why is it necessary to retest the program with cases that worked in the past?

Modification

11.18 Add output statements to the program to enable it to produce trace output automatically.

Testing

11.19 Summarize the categories of test cases used to test ReadRoman. Explain why the case that revealed the bug was missing.

Debugging

11.20 Create a complete list of categories of test cases for ReadRoman. Give examples of each. Explain why the list is complete.

Reflection

11.21 Even with this complete list of test cases, could the program still have an undetected bug? Why or why not?

Analysis

11.22 If your Python environment includes a debugger that allows you to interrupt a program at a designated point, describe good places at which this program could be interrupted to help debug it.

Analysis

11.23 What are the preconditions for the corrected version of ReadRoman?

Outline of Design and Development Questions

These questions summarize the main points of the commentary.

Understanding the Program
How does one start to evaluate this program?
What does the main program do?
What does ReadlnRoman do?
What does ReadRoman do?
Can we trace this function?
What is special about tracing recursive subprograms?
What values should be used to trace ReadRoman?
How does ReadRoman work on one-digit Roman numerals?
What does the trace reveal?
How does ReadRoman work on two-digit Roman numerals?
How does formatting help with tracing a recursive function?
What other aspects of the program can be tested with two-digit Roman numerals?
How does ReadRoman work on three-digit Roman numerals?
What does tracing ReadRoman reveal?
What template does ReadRoman use?
Can ReadRoman ever run off the end of the input line?

Testing the Program
What additional tests are needed?
What went wrong?
How can the bug be fixed?

A Possible Fix
What are the differences between the new version and the previous version?
Do the differences address the bug found in the first version?
Does the program handle all previously tested cases?
How should the revised code be analyzed?
What does a trace reveal?
What does the trace of ReadRoman reveal?
What are the test results?
What happens with a trace of XLIV?
What does the trace reveal?
What fix is needed?

Programmers' Summary

This case study discusses the analysis and testing of two solutions to the Roman Calculator Construction problem. Each solution includes a recursive function ReadRoman that reads Roman digits as it proceeds down the recursion, and that builds up the corresponding decimal value as it returns. The commentary illustrates several of the programming principles

Analysis of the first program follows the Divide and Conquer principle. As in The Calendar Shop, the program is analyzed by moving from the "big picture" to the details. In contrast, when analyzing the second solution to the problem, this principle suggests focusing on the revisions rather than completely reanalyzing the program.

The Divide and Conquer principle also prescribes an approach to testing. Following this principle, the program is first tested with small cases. When these are successful, testing builds on the results to test with larger and more complex cases that reduce to the smaller cases during program execution. This approach is especially important when analyzing recursive functions, since the goal is to notice the pattern of the computation and to be able to predict the result of the recursion without looking up the results of previous tests.

In tracing a recursion on paper, we follow the Multiple Representation principle by indenting the information for each recursive call. This representation, which resembles an outline, displays the structure of the recursion.

The Fingerprint, Literacy, and Recycling principles guide inspection of the code. Incorrect handling of end-of-line is a common source of errors, so we look for that in particular. Following the Literacy principle, we make sure that each variable name indicates its purpose correctly. We also look for familiar templates in the code. Errors often result from deviations from these patterns, or from code written without applying templates.

The ReadRoman function is based on the "read forward, process backward" pattern of processing. This template is illustrated in many introductory textbooks via the example of reading a line and printing it backward. It is an example of a more general recursive pattern:

if base case then:
return values immediately
otherwise:
set things up for the recursive call;
make the recursive call;
use the results of the recursive call
to construct values to return.

Bugs in both programs result from misapplication of this pattern. In the first program, the recursive call does not return enough information to construct a return value properly. In the revision, the recursive case returns two values and the base case (mistakenly) only one.

The bugs in these programs could have been detected if the Persecution Complex principle had been applied properly. The exercises guide the user of the case study to generate a complete set of test cases and to reflect on why it is important to test programs rigorously.

Making Sense of Roman Calculator Repair

Debugging

11.24 A version of the translation program converts XVI to 21 and XI to 11. What seems to be wrong with the program? List additional test cases and explain why they would help detect the problem.

Debugging

11.25 Which parts of the translation program should be inspected to locate the bug described in the previous question? Explain why.

Modification

11.26 Modify the translation program so that it prints the value of the Roman numeral in words. For example, V should be printed as "five"; C should be printed as "one hundred".

Debugging

11.27 Introduce a bug into the translation program such that some Roman numerals are translated correctly and others are translated incorrectly. Also construct as convincing a set of test data as you can that contains only values for which the program produces correct results. How many of your fellow programmers can you fool?

Debugging

11.28 What extra opportunities for mutations does a recursive subprogram present, compared to a nonrecursive subprogram?

Application

11.29 Use the "read forward, process backward" template in a program that reads a string of text, replaces any sequences of the same letters with a single letter, and prints it out backward. For example, rooommaaann becomes nomor; nnoaaammmooor becomes roman.

Testing

11.30 Test the revised version of ReadRoman with some illegal Roman numerals. Explain what happens.

Modification

11.31 Modify the translation program so that it detects all illegal Roman numerals and translates legal Roman numerals.

Application

11.32 Modern young Romans are having difficulty learning to interpret Roman numbers. Use the correct version of ReadRoman in a program that asks the user for a Roman numeral, asks for its decimal equivalent, and prints a message saying whether or not the translation was done correctly.

Application

11.33 Use the "read forward, process backward" template in a program that tests the contents of a string to see if it is a palindrome. A palindrome is a string that has the same sequence whether the characters are interpreted forward or backward. For example, "deed," "mom," and "94549" are palindromes.

Linking to Previous Case Studies

Analysis

11.34 Compare the recursive version of Roman numeral translation to the nonrecursive versions in Roman Calculator Construction. What are the advantages of a recursive solution?

Application

11.35 Describe how the "read forward, process backward" template could be used to solve the Space Text problem. Which solution do you prefer? Explain.

Application

11.36 Describe how the "read forward, process backward" template could be used to shuffle cards. When would this solution be advantageous?

Application

11.37 Implement a recursive version of the linear search algorithm.

Application

11.38 Implement a recursive version of the rule-confirmation approach to checking for Roman numerals.

Program to Solve the Roman Calculator Construction Problem

Note that the program has an input function for testing and that it assumes that the input data will be legal.

id = 0
romanDigits = ''
valToReturn = 0

def Translation (romanDigit):
return {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}.get(romanDigit, 0)

def ReadRoman():
global id
global romanDigits
global valToReturn
romanDigit = romanDigits[id]
romanInt = Translation (romanDigit)
id += 1
if id < len(romanDigits):
ReadRoman()
if romanInt < valToReturn:
valToReturn -= romanInt
else:
valToReturn += romanInt
else:
valToReturn = romanInt

def ReadlnRoman():
global romanDigits
global valToReturn
global id
romanDigits = input('Enter Roman Digits : ')
valToReturn = 0
id = 0
ReadRoman()
print (valToReturn)

# Main Program
while True:
ReadlnRoman()

An Attempt to Fix the Buggy Version

id = 0
romanDigits = ''
valToReturn = 0
lastRoman = 0

def Translation (romanDigit):
return {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}.get(romanDigit, 0)

def ReadRoman():
global id
global romanDigits
global valToReturn
global lastRoman
romanDigit = romanDigits[id]
romanInt = Translation (romanDigit)
id += 1
if id < len(romanDigits):
ReadRoman()
if romanInt < lastRoman:
valToReturn -= romanInt
else:
valToReturn += romanInt
lastRoman = romanInt
else:
valToReturn = romanInt
lastRoman = romanInt

def ReadlnRoman():
global romanDigits
global valToReturn
global id
global lastRoman
romanDigits = input('Enter Roman Digits : ')
valToReturn = 0
lastRoman = 0
id = 0
ReadRoman()
print (valToReturn)

# Main Program
while True:
ReadlnRoman()